#include <vector>
#include <iostream>

using namespace std;

/* 0-1 背包：空间优化后的动态规划 */
int knapsackDPComp(vector<int> &wgt, vector<int> &val, vector<int> &used_wgt, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                int no = dp[c]; // 不选物品 i
                int yes = dp[c - wgt[i - 1]] + val[i - 1]; // 选物品 i
                if (yes > no) {
                    dp[c] = yes;
                    used_wgt[c] = used_wgt[c - wgt[i - 1]] + wgt[i - 1];
                } else {
                    dp[c] = no;
                }
                // dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

int main() {
    vector<int> wgt = {2, 2, 3 };
    vector<int> val = {5, 11, 15};
    int cap = 6;
    vector<int> used_wgt(cap+1, 0);
    int total = knapsackDPComp(wgt, val, used_wgt, cap);
    cout << "val: " << total << ", left wgt: " << cap - used_wgt.back() << endl;
    return 0;
}